package ua.mykola.graph;

import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;

public abstract class FirstSearch {
	protected Set<Vertex> visited = new HashSet<Vertex>();
	protected Vertex topVertex;
	protected Map<Vertex, Edge> pathUp = new HashMap<Vertex, Edge>();
	protected Graph graph;

	public FirstSearch(Graph graph, Vertex vertex) {
		this.graph = graph;
		this.topVertex = vertex;
	}

	public FirstSearch(Graph graph, String vertexLabel) {
		this(graph, new Vertex(vertexLabel));
	}

	public void traverse() {
		traverse(topVertex);
	}

	protected abstract void traverse(Vertex vertex);

	public boolean hasPathTo(Vertex vertex) {
		return visited.contains(vertex);
	}

	public boolean hasPathTo(String label) {
		return visited.contains(new Vertex(label));
	}

	public List<Edge> pathTo(String label) {
		LinkedList<Edge> path = null;
		Vertex currentVertex = new Vertex(label);
		Edge edgeUp;
		if (hasPathTo(label)) {
			path = new LinkedList<Edge>();
			while (!topVertex.equals(currentVertex)) {
				edgeUp = pathUp.get(currentVertex);
				path.addFirst(edgeUp);
				currentVertex = edgeUp.getOtherSide(currentVertex);
			}
		}
		return path;
	}

}
